import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-04-02
 * Time: 9:44
 */

class Solution {
    public int[] twoSum(int[] nums, int target) {

        // 定义头指针 left
        int left = 0;

        // 定义尾指针 right
        int right = nums.length - 1;


        // 移动 left 和 right ，直到 left 在 right 右侧或者相遇为止
        while(left < right) {

            // 计算此时两个指针指向的元素值之和
            int sum = nums[left] + nums[right];

            // 如果这两个元素值之和小于目标值 target
            if(sum < target){

                // 由于数组是递增排序的数组
                // 所以需要去找更大的数，那 left 向右移动
                left++;

                // 如果这两个元素值之和大于目标值 target
            } else if(sum > target) {

                // 由于数组是递增排序的数组
                // 所以需要去找更小的数，那 right 向左移动
                right--;

                // 如果这两个元素值之和等于目标值 target
            } else{

                // 说明找到一对符合要求的数
                // 返回即可
                return new int[] { nums[left], nums[right] };
            }
        }

        // 否则说明没有找到
        return new int[0];
    }
}


class Solution1 {
    public int missingNumber(int[] nums) {


        // left 指向当前区间的最左边位置，所以初始化为 0
        int left = 0 ;

        // right 指向当前区间的最右边位置，所以初始化为 nums.length - 1
        int right = nums.length - 1;

        // 循环进行二分查找，直到左端点位置超过了右端点
        while( left <= right ) {

            // 计算当前区间的中间位置，向下取整
            int mid = (left + right) / 2;

            // 如果中间位置的元素值等于当前索引的值
            // 那么说明从 left 到 mid 的这些元素都在正确的位置上
            // 即从 left 到 mid 的这些数字都在数组中，没有发生缺失
            // 所以需要在 mid + 1 到 right 这个区间去查找缺失的数字
            if(nums[mid] == mid){

                // 缩小范围为 mid + 1 到 right
                // 当前区间的左侧为 left = mid + 1，右侧 right
                left = mid + 1;

                // 否则，说明从 left 到 mid 的这些元素，有元素不在正确的位置上
                // 即从 left 到 mid 的这些数字有数字发生缺失
                // 所以需要在 left 到 mid - 1 这个区间去查找缺失的数字
            }else{

                // 所以缩小范围为 left 到 mid - 1
                // 当前区间的左侧为 left，右侧 right = mid - 1
                right = mid - 1;

            }
        }

        // 由于只有一个数字缺失，所以找到的时候，left 指向的那个数字就是，使得后面所有数字与索引不一一对应时的第一个数字
        // 返回就行
        return left;
    }
}

class Solution3 {
    public int[] spiralOrder(int[][] matrix) {

        // 特殊情况，边界处理，比如 matrix = []，无法获取  matrix[0]
        if (matrix.length == 0) {
            return new int[0];
        }

        // 设置一个一维数组 res 用来记录二维数组 matrix 中的顺时针打印的结果
        int[] res = new int[matrix.length * matrix[0].length];

        // 在打印的过程中，不断的缩小着打印的区间
        // 每当把从左到右把一行打印完毕之后，整个矩阵就在顶部少了一层，后续打印不需要再去处理它们
        // 每当把从上到下把一列打印完毕之后，整个矩阵就在右部少了一列，后续打印不需要再去处理它们
        // 每当把从右到左把一行打印完毕之后，整个矩阵就在底部少了一层，后续打印不需要再去处理它们
        // 每当把从下到上把一列打印完毕之后，整个矩阵就在左部少了一列，后续打印不需要再去处理它们
        // 因此，设置四个变量，用来记录打印的区间变化

        // top 表示顶部所在的层数位置，一开始在第 0 层
        int top = 0 ;

        // bottom 表示底部所在的层数位置，一开始在第 matrix.length - 1 层
        int bottom = matrix.length - 1 ;

        // left 表示左部所在的列数位置，一开始在第 0 列
        int left = 0 ;

        // right 表示右部所在的列数位置，一开始在第 matrix[0].length - 1 列
        int right = matrix[0].length - 1;

        // 顺时针打印矩阵过程中，填充 res 数组，从索引位置 0 的地方开始填充
        int index = 0;

        // 使用一个 while 循环进行打印，只要打印区间中还有值就一直打印
        // 直到出现边界越界，即打印区间不存在元素了，跳出循环
        while (true) {

            // 1、从左到右，打印这一行
            // 此时，边界从 left 到 right
            for (int i = left; i <= right; i++) {

                // 将当前元素填充到 res 中
                // 此时，一直都是在 top 这一层
                res[index] = matrix[top][i];

                // index 的元素填充完毕之后，开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后，此时，顶部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了，因此，将 top 的层数向下挪
            top += 1;

            // 如果此时发现顶部位置越过了底部位置，说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( top > bottom ) {
                break;
            }

            // 2、从上到下，打印这一列
            // 此时，边界从 top 到 bottom
            for (int i = top; i <= bottom; i++) {

                // 将当前元素填充到 res 中
                // 此时，一直都是在 right 这一列
                res[index] = matrix[i][right];

                // index 的元素填充完毕之后，开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后，此时，右部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了，因此，将 right 的层数向左挪
            right -= 1;

            // 如果此时发现右部位置越过了左部位置，说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( right < left ) {
                break;
            }

            // 3、从右到左，打印这一行
            // 此时，边界从 right 到 left
            for (int i = right; i >= left; i--) {

                // 将当前元素填充到 res 中
                // 此时，一直都是在 bottom 这一层
                res[index] = matrix[bottom][i];

                // index 的元素填充完毕之后，开始填充下一个元素
                index++;

            }

            // 经过上面这个循环之后，此时，底部这一层的所有元素已经打印完毕
            // 整个打印区间需要删除这一行了，因此，将 bottom 的层数向上挪
            bottom -= 1;

            // 如果此时发现顶部位置越过了底部位置，说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( bottom < top ) {
                break;
            }

            // 4、从下到上，打印这一列
            // 此时，边界从 bottom 到 top
            for (int i = bottom; i >= top; i--) {

                // 将当前元素填充到 res 中
                // 此时，一直都是在 left 这一列
                res[index] = matrix[i][left];

                // index 的元素填充完毕之后，开始填充下一个元素
                index++;
            }

            // 经过上面这个循环之后，此时，左部这一列的所有元素已经打印完毕
            // 整个打印区间需要删除这一列了，因此，将 left 的层数向右挪
            left += 1;

            // 如果此时发现右部位置越过了左部位置，说明整个打印区间已经没有元素了
            // 跳出循环即可
            if ( left > right ) {
                break;
            }

        }

        // 最后，返回结果即可
        return res;
    }
}



public class TestDemo {

    public static void main(String[] args) {
        System.out.println(Math.sqrt(16));
    }
}
